//241 Different Ways to Add Parentheses
/*
给定一个只包含加、减和乘法的数学表达式，求通过加括号可以得到多少种不同的结果

输入输出样例
	输入是一个字符串，表示数学表达式；输出是一个数组，存储所有不同的加括号结果

Input: "2-1-1"
Output: [0, 2]

*/
#include <vector>
using namespace std;
vector<int> diffWaysToCompute(string input)
{
	vector<int> data;
	vector<char> ops;
	int num = 0;
	char op = ' ';
	istringstream ss(input + "+");
	while (ss >> num && ss >> op)
	{
		data.push_back(num);
		ops.push_back(op);
	}
	int n = data.size();
	vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>()));
	for (int i = 0; i < n; ++i)
	{
		for (int j = i; j >= 0; --j)
		{
			if (i == j)
			{
				dp[j][i].push_back(data[i]);
			}
			else
			{
				for (int k = j; k < i; k += 1)
				{
					for (auto left : dp[j][k])
					{
						for (auto right : dp[k + 1][i])
						{
							int val = 0;
							switch (ops[k])
							{
							case ' + ':
								val = left + right;
								break;
							case ' - ':
								val = left - right;
								break;
							case '*':
								val = left * right;
								break;
							}
							dp[j][i].push_back(val);
						}
					}
				}
			}
		}
	}
	return dp[0][n - 1];
}

//932
//312